package org.example.SolutionNew004;

import java.util.*;

public class GraphTheory003 {
    public static void main(String[] args) {
        GraphTheory003 graph = new GraphTheory003();
        int[][] nums=new int[][]{{0,2},{1,2},{3,2},{3,4}};
        System.out.println(graph.canFinish(5,nums));
    }

    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        List<Set<Integer>> list=new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            Set<Integer> temp=new HashSet<>();
            list.add(temp);
        }
        for(int[] p:prerequisites){
            int a=p[0],b=p[1];
            list.get(a).add(b);
        }
        int count=numCourses;
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(list.get(i).isEmpty()){
                count--;
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            int temp=queue.poll();
            for(int i=0;i<numCourses;i++){
                if(list.get(i).contains(temp)){
                    list.get(i).remove(temp);
                    if(list.get(i).isEmpty()){
                        count--;
                        queue.add(i);
                    }
                }
            }
        }
        return count <= 0;
    }

    boolean valid;
    int[] visited;
    List<List<Integer>> list;

    //深度+拓扑排序
    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        valid=true;
        list=new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            List<Integer> temp=new ArrayList<>();
            list.add(temp);
        }
        for(int[] p:prerequisites){
            int a=p[0],b=p[1];
            list.get(b).add(a);
        }
        visited=new int[numCourses];
        for(int i=0;i<numCourses && valid;i++){
            if(visited[i]==0){
                dfs(i);
            }
        }

        return valid;
    }

    public void dfs(int i){
        visited[i]=1;
        for(int tmp:list.get(i)){
            if(visited[tmp]==0){
                dfs(tmp);
                if(!valid) return;
            }else if(visited[tmp]==1){
                valid=false;
                return;
            }
        }
        visited[i]=2;
    }

    //广度+拓扑排序
    List<List<Integer>> l;
    int[] indeg;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        l=new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            List<Integer> temp=new ArrayList<>();
            l.add(temp);
        }
        indeg=new int[numCourses];
        for(int[] p:prerequisites){
            int a=p[0],b=p[1];
            l.get(b).add(a);
            ++indeg[a];
        }
        Queue<Integer> queue=new LinkedList<>();
        int count=0;
        for(int i=0;i<numCourses;i++){
            if(indeg[i]==0){
                queue.add(i);
                count++;
            }
        }
        while(!queue.isEmpty()){
            int temp=queue.poll();
            for(int v:l.get(temp)){
                indeg[v]--;
                if(indeg[v]==0){
                    queue.add(v);
                    count++;
                }
            }
        }
        return count==numCourses;
    }
}
